package com.tgy.algorithm.base._动态规划;


/**
 * 两个字符串的最长公共子序列问题
 */
public class _最长公共子序列 {


    public static int mcsq(String firstContent, String secondContent) {

        int firstLen = firstContent.length();
        int secondLen = secondContent.length();
        char[] firstArr = firstContent.toCharArray();
        char[] secondArr = secondContent.toCharArray();
        int[][] dp = new int[firstLen][secondLen];


        boolean beforeEq = false;
        for (int i = 0; i < secondLen; i++) {
            // 先填写第一行
//            dp[0][i] = secondArr[i] == firstArr[];
//            dp[0][i] = beforeEq ? 1:(secondArr[i] == firstArr[0]?1:0);
            if (beforeEq) {
                dp[0][i] = 1;
            }else {
                if (secondArr[i] == firstArr[0]) {
                    beforeEq = true;
                    dp[0][i] = 1;
                }
            }
        }

        beforeEq = false;
        for (int i = 0; i < firstLen; i++) {
            if (beforeEq) {
                dp[i][0] = 1;
            }else {
                if (secondArr[0] == firstArr[i]){
                    beforeEq = true;
                    dp[i][0] = 1;
                }
            }
        }


        for (int i = 1; i < firstLen; i++) {
            for (int j = 1; j < secondLen; j++) {

                int value = Math.max(dp[i-1][j],dp[i][j-1]);
                if (firstArr[i] != secondArr[j]) {
                    value = Math.max(value,dp[i-1][j-1]);
                }else {
                    value = Math.max(value,dp[i-1][j-1]+1);
                }

                dp[i][j] = value;
            }
        }

        return dp[firstLen-1][secondLen-1];
    }

    public static void main(String[] args) {
        String first = "a1b2c";
        String second = "ac1dbf2dc";
        int mcsq = mcsq(first, second);
        System.out.println(mcsq);
    }
}
